package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 438. 找到字符串中所有字母异位词
 * @date 2025/2/20 23:08
 */
public class E438 {

    /**
     * 滑动窗口
     * @param s 源字符串
     * @param p 模式字符串
     * @return 包含所有字母异位词的起始索引的列表
     */
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> result = new ArrayList<>();
        // 如果 s 比 p 短，直接返回空列表
        if (s.length() < p.length()) return result;
        // 初始化两个数组，用于存储 p 和当前窗口的字符频率
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        // 计算 p 中每个字符的频率
        for (char c : p.toCharArray()) pCount[c - 'a']++;
        // 滑动窗口遍历字符串 s
        for (int i = 0; i < s.length(); i++) {
            // 增加窗口右边界的字符
            sCount[s.charAt(i) - 'a']++;
            // 当窗口大小超过 p 的长度时，移除窗口左边界的字符
            if (i >= p.length()) sCount[s.charAt(i - p.length()) - 'a']--;
            // 比较当前窗口的字符频率是否与 p 的字符频率相同
            if (i >= p.length() - 1 && matches(pCount, sCount)) result.add(i - p.length() + 1);
        }
        return result;
    }

    /**
     * 比较两个数组是否相等
     * @param a 数组 a
     * @param b 数组 b
     * @return 如果两个数组相等，则返回 true，否则返回 false
     */
    private boolean matches(int[] a, int[] b) {
        for (int i = 0; i < 26; i++)
            if (a[i] != b[i]) return false;
        return true;
    }

    /**
     * 滑动窗口
     * @param s 源字符串
     * @param p 模式字符串
     * @return 包含所有字母异位词的起始索引的列表
     */
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> result = new ArrayList<>();
        char[] pattern = p.toCharArray();
        char[] source = s.toCharArray();
        int[] countPattern = new int[26];
        int[] countSource = new int[26];
        if(pattern.length > source.length) return result;
        for(char c : pattern) countPattern[c - 'a']++;
        int left = 0, right = 0;
        while(right < pattern.length)
            countSource[source[right++] - 'a']++;
        while(right < source.length){
            if(match(countPattern, countSource)) result.add(left);
            countSource[source[left++] - 'a']--;
            countSource[source[right++] - 'a']++;
        }
        if(match(countPattern, countSource)) result.add(left);
        return result;
    }

    /**
     * 比较两个数组是否相等
     * @param arr1 数组 a
     * @param arr2 数组 b
     * @return 如果两个数组相等，则返回 true，否则返回 false
     */
    private boolean match(int[] arr1, int[] arr2){
        for(int i = 0; i < arr1.length; i++)
            if(arr1[i] != arr2[i]) return false;
        return true;
    }
}
